package com.yanceysong.codetop.s61_s70;

public class S69_Mid_64_最小路径和 {
    /**
     * .S69_Mid_64_最小路径和
     * .<p>
     * .题目链接：<a href="https://leetcode.cn/problems/minimum-path-sum/">LeetCode 64. 最小路径和</a>
     * .<p>
     * .【题目描述】
     * .给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角 (0,0) 到右下角 (m-1,n-1) 的路径，使得路径上的数字总和最小。
     * .移动规则：每次只能向 右 或 向 下 移动一格。
     * .<p>
     * .【核心标签】动态规划 / 二维数组 / 空间优化
     * .<p>
     * .【示例 1】
     * .输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
     * .路径：1 → 3 → 1 → 1 → 1  (或 1 → 1 → 5 → 1 → 1 等，但最优是 7)
     * .输出：7
     * .<p>
     * .【示例 2】
     * .输入：grid = [[1,2,3],[4,5,6]]
     * .最优路径：1 → 2 → 3 → 6，总和 = 12
     * .输出：12
     * .<p>
     * .【示例 3】单行或单列：
     * .输入：grid = [[5,1,9]] 只能向右 => 5+1+9 = 15
     * .输入：grid = [[5],[1],[9]] 只能向下 => 5+1+9 = 15
     * .<p>
     * .【边界情况】
     * .1. 空数组 或 行列之一为 0 => 返回 0
     * .2. 只有 1 个元素 => 直接返回该元素
     * .<p>
     * .=============================================
     * .【思路一：二维 DP】
     * .定义：dp[i][j] 表示到达格子 (i,j) 的最小路径和。
     * .转移：只能从 上方 (i-1,j) 或 左侧 (i,j-1) 来：
     * .     dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
     * .初始：
     * .     dp[0][0] = grid[0][0]
     * .     第一行只能从左向右累加，第一列只能从上向下累加。
     * .答案：dp[m-1][n-1]
     * .<p>
     * .【ASCII 图解】示例 grid = [[1,3,1],[1,5,1],[4,2,1]]
     * . 原始网格：
     * .     1   3   1
     * .     1   5   1
     * .     4   2   1
     * . dp 填表过程：
     * . 第 0 行累加：1  4  5
     * . 第 0 列累加：1  2  6
     * . 位置 (1,1): min(4,2)+5 = 7
     * . 位置 (1,2): min(5,7)+1 = 6
     * . 位置 (2,1): min(7,6)+2 = 8
     * . 位置 (2,2): min(6,8)+1 = 7 (答案)
     * . 最终 dp：
     * .     1   4   5
     * .     2   7   6
     * .     6   8   7
     * .<p>
     * .【关键洞察】
     * .1. 每个格子只依赖 上 + 左 两个方向 => 典型二维 DP；
     * .2. 若希望节省空间，可以使用一维数组滚动更新；
     * .3. 因为权值非负，贪心不能简单使用（局部小不一定整体最优），必须 DP；
     * .4. 与「不同路径」题类似，区别是这里是加权累加最小值；
     * .5. 空间优化后时间复杂度不变，仅内存降为 O(n)。
     * .<p>
     * .【复杂度分析】
     * .时间复杂度：O(m * .n)，每个格子访问一次。
     * .空间复杂度：O(m * .n)（二维 DP），可优化为 O(n)（一维滚动数组）。
     * .<p>
     * .【思路二：空间优化（滚动数组）】
     * .用一维数组 dp[j] 表示当前行到达列 j 的最小路径和；
     * .更新规则：dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
     * .注意：dp[j] 原值对应上方；dp[j-1] 对应左侧。
     * .<p>
     * .【适用场景】
     * .- 网格规模较大时，推荐空间优化版本；
     * .- 当需要输出路径本身时，需要额外记录前驱；本题仅求和无需记录。
     * .<p>
     * .【可能的扩展】
     * .- 若允许向左/向上/对角线移动 => 状态转移需扩展；
     * .- 若有障碍（不可通行）=> 需跳过或设置为无穷大；
     * .- 若要返回路径 => 需维护 parent 数组或逆推。
     */
    public int minPathSum(int[][] grid) {
        // 基础边界检查：防止空指针或非法输入
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        // 行数
        int rows = grid.length;
        // 列数
        int cols = grid[0].length;

        // dpTable[i][j] 含义：从 (0,0) 到 (i,j) 的最小路径和
        int[][] dpTable = new int[rows][cols];

        // 起点初始化：起点的最小路径和就是自身数值
        dpTable[0][0] = grid[0][0];

        // 第一列：只能从上往下累加 => dpTable[row][0] = dpTable[row-1][0] + grid[row][0]
        for (int row = 1; row < rows; row++) {
            dpTable[row][0] = dpTable[row - 1][0] + grid[row][0];
        }

        // 第一行：只能从左往右累加 => dpTable[0][col] = dpTable[0][col-1] + grid[0][col]
        for (int col = 1; col < cols; col++) {
            dpTable[0][col] = dpTable[0][col - 1] + grid[0][col];
        }

        // 其余位置：只能来自 上方(row-1,col) 或 左侧(row,col-1) 的较小路径和再加当前值
        for (int row = 1; row < rows; row++) {
            for (int col = 1; col < cols; col++) {
                int fromTop = dpTable[row - 1][col];   // 上方的最小路径和
                int fromLeft = dpTable[row][col - 1];   // 左侧的最小路径和
                dpTable[row][col] = Math.min(fromTop, fromLeft) + grid[row][col];
            }
        }

        // 返回终点的最小路径和
        return dpTable[rows - 1][cols - 1];
    }

    /**
     * .空间优化版本：使用一维滚动数组
     * .dp[col] 表示当前处理到的行的列 col 的最小路径和
     */
    public int minPathSumOptimized(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length;
        int cols = grid[0].length;
        // minPathSums[col] 表示当前行到达列 col 的最小路径和
        int[] minPathSums = new int[cols];

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (row == 0 && col == 0) {
                    minPathSums[col] = grid[0][0]; // 起点
                } else if (row == 0) {
                    // 第一行：只能从左侧过来
                    minPathSums[col] = minPathSums[col - 1] + grid[row][col];
                } else if (col == 0) {
                    // 第一列：只能从上方过来（此时 minPathSums[col] 仍是上一行该列的最小路径和）
                    minPathSums[col] = minPathSums[col] + grid[row][col];
                } else {
                    // 当前位置最小路径和 = min(来自上方, 来自左侧) + 当前格子值
                    minPathSums[col] = Math.min(minPathSums[col], minPathSums[col - 1]) + grid[row][col];
                }
            }
        }
        return minPathSums[cols - 1];
    }

    public static void main(String[] args) {
        S69_Mid_64_最小路径和 solution = new S69_Mid_64_最小路径和();
        System.out.println("=== 最小路径和测试开始 ===");

        // 测试 1：题目示例 1
        System.out.println("\n--- 测试1: 示例 [[1,3,1],[1,5,1],[4,2,1]] ---");
        int[][] grid1 = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        int ans1 = solution.minPathSum(grid1);
        int ans1Opt = solution.minPathSumOptimized(grid1);
        System.out.println("minPathSum -> " + ans1 + " (期望: 7)");
        System.out.println("minPathSumOptimized -> " + ans1Opt + " (期望: 7)");
        assert ans1 == 7 && ans1Opt == 7 : "示例1失败";
        System.out.println("✓ 示例1通过");

        // 测试 2：示例 2
        System.out.println("\n--- 测试2: 示例 [[1,2,3],[4,5,6]] ---");
        int[][] grid2 = {{1, 2, 3}, {4, 5, 6}};
        int ans2 = solution.minPathSum(grid2);
        int ans2Opt = solution.minPathSumOptimized(grid2);
        System.out.println("minPathSum -> " + ans2 + " (期望: 12)");
        System.out.println("minPathSumOptimized -> " + ans2Opt + " (期望: 12)");
        assert ans2 == 12 && ans2Opt == 12 : "示例2失败";
        System.out.println("✓ 示例2通过");

        // 测试 3：单行
        System.out.println("\n--- 测试3: 单行 [[5,1,9]] ---");
        int[][] grid3 = {{5, 1, 9}};
        int ans3 = solution.minPathSum(grid3);
        int ans3Opt = solution.minPathSumOptimized(grid3);
        System.out.println("minPathSum -> " + ans3 + " (期望: 15)");
        System.out.println("minPathSumOptimized -> " + ans3Opt + " (期望: 15)");
        assert ans3 == 15 && ans3Opt == 15 : "单行失败";
        System.out.println("✓ 单行测试通过");

        // 测试 4：单列
        System.out.println("\n--- 测试4: 单列 [[5],[1],[9]] ---");
        int[][] grid4 = {{5}, {1}, {9}};
        int ans4 = solution.minPathSum(grid4);
        int ans4Opt = solution.minPathSumOptimized(grid4);
        System.out.println("minPathSum -> " + ans4 + " (期望: 15)");
        System.out.println("minPathSumOptimized -> " + ans4Opt + " (期望: 15)");
        assert ans4 == 15 && ans4Opt == 15 : "单列失败";
        System.out.println("✓ 单列测试通过");

        // 测试 5：单个元素
        System.out.println("\n--- 测试5: 单元素 [[42]] ---");
        int[][] grid5 = {{42}};
        int ans5 = solution.minPathSum(grid5);
        int ans5Opt = solution.minPathSumOptimized(grid5);
        System.out.println("minPathSum -> " + ans5 + " (期望: 42)");
        System.out.println("minPathSumOptimized -> " + ans5Opt + " (期望: 42)");
        assert ans5 == 42 && ans5Opt == 42 : "单元素失败";
        System.out.println("✓ 单元素测试通过");

        // 测试 6：包含 0 值
        System.out.println("\n--- 测试6: 包含0值 [[0,2,2],[3,0,1],[4,2,0]] ---");
        int[][] grid6 = {{0, 2, 2}, {3, 0, 1}, {4, 2, 0}};
        int ans6 = solution.minPathSum(grid6);
        int ans6Opt = solution.minPathSumOptimized(grid6);
        System.out.println("minPathSum -> " + ans6 + " (期望: 3)");
        System.out.println("minPathSumOptimized -> " + ans6Opt + " (期望: 3)");
        assert ans6 == 3 && ans6Opt == 3 : "包含0值失败";
        System.out.println("✓ 包含0值测试通过");

        // 测试 7：较大矩阵
        System.out.println("\n--- 测试7: 较大矩阵 ---");
        int[][] grid7 = {
                {1, 4, 8, 6, 2, 2, 1, 7},
                {4, 7, 3, 7, 9, 6, 4, 2},
                {7, 3, 7, 9, 3, 5, 7, 9},
                {1, 7, 9, 4, 8, 3, 2, 6},
                {2, 3, 6, 6, 4, 5, 1, 8},
                {3, 5, 7, 3, 6, 7, 5, 9},
                {1, 6, 8, 2, 3, 4, 7, 1},
                {2, 4, 1, 9, 8, 1, 5, 7}
        };
        int ans7 = solution.minPathSum(grid7);
        int ans7Opt = solution.minPathSumOptimized(grid7);
        System.out.println("minPathSum -> " + ans7);
        System.out.println("minPathSumOptimized -> " + ans7Opt);
        assert ans7 == ans7Opt : "较大矩阵两种方法结果不一致";
        System.out.println("✓ 较大矩阵测试通过 (结果:" + ans7 + ")");

        // 测试 8：空 grid
        System.out.println("\n--- 测试8: 空矩阵 new int[0][0] ---");
        int[][] grid8 = new int[0][0];
        int ans8 = solution.minPathSum(grid8);
        int ans8Opt = solution.minPathSumOptimized(grid8);
        System.out.println("minPathSum -> " + ans8 + " (期望: 0)");
        System.out.println("minPathSumOptimized -> " + ans8Opt + " (期望: 0)");
        assert ans8 == 0 && ans8Opt == 0 : "空矩阵失败";
        System.out.println("✓ 空矩阵测试通过");

        // 测试 9：含大数验证累加正确性
        System.out.println("\n--- 测试9: 大数 [[1000,2000],[3000,4000]] ---");
        int[][] grid9 = {{1000, 2000}, {3000, 4000}}; // 1000->2000->4000=7000 vs 1000->3000->4000=8000
        int ans9 = solution.minPathSum(grid9);
        int ans9Opt = solution.minPathSumOptimized(grid9);
        System.out.println("minPathSum -> " + ans9 + " (期望: 7000)");
        System.out.println("minPathSumOptimized -> " + ans9Opt + " (期望: 7000)");
        assert ans9 == 7000 && ans9Opt == 7000 : "大数失败";
        System.out.println("✓ 大数测试通过");

        // 测试 10：不规则数值分布避免贪心误判
        System.out.println("\n--- 测试10: 反贪心验证 [[1,100,1],[1,100,1],[1,1,1]] ---");
        int[][] grid10 = {{1, 100, 1}, {1, 100, 1}, {1, 1, 1}}; // 若贪心右走会错，最优路径是下下右右右 => 1+1+1+1+1+1=6
        int ans10 = solution.minPathSum(grid10);
        int ans10Opt = solution.minPathSumOptimized(grid10);
        System.out.println("minPathSum -> " + ans10 + " (期望: 6)");
        System.out.println("minPathSumOptimized -> " + ans10Opt + " (期望: 6)");
        assert ans10 == 6 && ans10Opt == 6 : "反贪心验证失败";
        System.out.println("✓ 反贪心验证测试通过");

        // 新增 测试 11：随机小矩阵交叉验证两种实现一致性
        System.out.println("\n--- 测试11: 随机矩阵一致性校验 (100 轮) ---");
        java.util.Random rand = new java.util.Random(64); // 固定种子保证可复现
        for (int t = 1; t <= 100; t++) {
            int r = 1 + rand.nextInt(6);      // 行数 1~6
            int c = 1 + rand.nextInt(6);      // 列数 1~6
            int[][] g = new int[r][c];
            for (int i = 0; i < r; i++) {
                for (int j = 0; j < c; j++) {
                    g[i][j] = rand.nextInt(11); // 元素 0~10
                }
            }
            int a = solution.minPathSum(g);
            int b = solution.minPathSumOptimized(g);
            if (a != b) {
                System.out.println("随机测试失败 第" + t + "轮 行=" + r + " 列=" + c);
                throw new AssertionError("随机矩阵结果不一致");
            }
        }
        System.out.println("✓ 随机矩阵一致性全部通过");

        // 新增 测试 12：全 0 矩阵
        System.out.println("\n--- 测试12: 全0矩阵 [[0,0,0],[0,0,0]] ---");
        int[][] grid12 = {{0, 0, 0}, {0, 0, 0}};
        int ans12 = solution.minPathSum(grid12);
        int ans12Opt = solution.minPathSumOptimized(grid12);
        System.out.println("minPathSum -> " + ans12 + " (期望: 0)");
        System.out.println("minPathSumOptimized -> " + ans12Opt + " (期望: 0)");
        assert ans12 == 0 && ans12Opt == 0 : "全0矩阵失败";
        System.out.println("✓ 全0矩阵测试通过");

        System.out.println("\n=== 所有测试完成 ===");
    }
}
